#coding:utf-8

'''
email: chenyan@feling.net

插入排序(从小到大)

数据量小的时候，大概30个左右，可以用这个

'''

def insertion_sort(l):
    '''
    直接排序传进来的列表，而不是产生一个新的列表
    >>> l = [2,8,5,4,8,9,1,7]
    >>> insertion_sort(l) 
    >>> l
    [1, 2, 4, 5, 7, 8, 8, 9]
    '''
    curr = 1
    while curr<len(l):
        tcurr = curr
        while tcurr>0:
            if l[tcurr]<l[tcurr-1]:
                l[tcurr], l[tcurr-1] = l[tcurr-1], l[tcurr]
            else:
                break
            tcurr -= 1
        curr += 1

if __name__=='__main__':
    import doctest
    doctest.testmod()
